#include <stdio.h>
#include <stdlib.h>

typedef struct BNode{
    BNode * lchild;
    BNode * rchild;
    int data;
}BNode,*BTree;

/** key = 5
 *              1
 *          2       3
 * */

BNode * getParent(BTree T, BNode *node){
    if(T == NULL)
        return NULL;

    if (T->lchild == node || T->rchild == node)
        return T;

    BNode *node1 = getParent(T->lchild, node);
    if (node1)
        return node1;

    BNode *node2 = getParent(T->rchild, node);
    if (node2)
        return node2;
    
    return NULL;
}



void visit(BTree T, BNode *node){
    if (T->lchild == node || T->rchild == node)
        parent = T;
}

void getParent4(BTree T, BNode *node) {
    if (!T) {
        visit(T, node);
        getParent4(T->lchild, node);
        getParent4(T->rchild, node);
    }
}

//该函数返回值的含义：是否要告诉上一层，这一层的结果
BNode *parent = NULL;
bool getParent2(BTree T, int x) {
    if (!T)
        return false;
    if (T->data == x)
        return true;
    if (getParent2(T->lchild, x) || getParent2(T->rchild, x))
        parent = T;
    return false;
}

// BTree * visit(T){
//     if()
// }
// BTree * getParent3(BTree T,int x){
//     if(T != NULL)
//     {
//         visit(T);
//     }
// }


// 测试
void print(BTree T) {
    if (T) {
        printf("%d ",T->data);
        print(T->lchild);
        print(T->rchild);
    }
}

BNode * GetNode(int x) {
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
}

int main() {
    BTree T = GetNode(1);
    T->lchild = GetNode(2);
    T->rchild = GetNode(3);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);

    print(T);
    getParent2(T, 5);

    printf("===> %d ", parent->data);

    BNode *node = getParent(T, T->lchild->lchild);
    printf("===> %d ", node->data);
    return 0;
}